// MergeSort.java

package com.ibm.tspaces.examples.mergesort;

import	java.util.*;
import	com.ibm.tspaces.*;

/*
**  Licensed Materials - Property of IBM
**
**  (C) COPYRIGHT IBM Corp. 1997  All rights reserved
**
**  US Government Users Restricted Rights - Use, duplication or
**  disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
**
**/

/**
** This class implements a merge sort using TupleSpace.  It is an
** example of how to use the com.ibm.tspaces package.
** It generates a number of random integers and then uses TupleSpace
** as a communication medium to coordinate the activities of a
** number of threads that perform the actual sorting/merging.
** 
** @see Tuple
** @see Field
** @see TupleSpace
** @version $Revision: 2.1.2.1 $ $Date: 2000/08/30 12:54:18 $
** @author Daniel Ford
*/

public class MergeSort extends Thread {

  /*
  ***************************************************************************
  ** ** Members **
  ** *************
  **
  */

  /**
  ** The default number of integers to be randomly generated and then sorted.
  */
  private static final int	DEFAULTNUMINTSTOSORT = 10;

  /**
  ** The default maxium value of the integers to be sorted.
  */
  private static final int	DEFAULTMAXINTVALUE = 1000;

  /**
  ** The default number of threads to be started that perform the actual sorting.
  */
  private static final	int	DEFAULTNUMSORTTHREADS	= 2;

  /**
  ** The default name of the tuple space to use to do the sorting in.
  */
  public static final String	DEFAULTSPACENAME	= "mergesort";

  /**
  ** The default name of the server hosting the tuple space for the sort.
  */
  public static final String	DEFAULTSERVERNAME	= "localhost";
  
  
  /**
  ** The number of integers to sort.
  */
  private	int		numberOfInts							=	0;

  /**
  ** The maximum value of any integer to be sorted
  */
  private	int		maxIntValue								=	0;

  /**
  ** The number of threads to be used to sort the integers	
  */
  private	int		numberOfSortThreads						=	0;
  private SortThread[] _st                 = null;
  /**
  ** The name of the TupleSpace to be used to do the sorting
  */
  private	String	spaceName								=	"";

  /**
  ** The name of the server that hosts the tuple space	
  */
  private	String	serverName								=	"";

  /*
  ***************************************************************************
  ** ** MergeSort **
  ** ***************
  */
  /**
  ** Sort a set of randomly generated integers.
  ***************************************************************************
  */
  public MergeSort( ) {
    this( DEFAULTNUMINTSTOSORT );
  } // MergeSort

  /*
  ***************************************************************************
  ** ** MergeSort **
  ** ***************
  */
  /**
  ** Sort a set of randomly generated integers.
  **
  ** @param numberOfInts the number of random integers to generate and then
  **		sort.
  ***************************************************************************
  */
  public MergeSort( int numberOfInts ) {
    this( numberOfInts, DEFAULTSERVERNAME );
  } // MergeSort

  /*
  ***************************************************************************
  ** ** MergeSort **
  ** ***************
  */
  /**
  ** Sort a set of randomly generated integers.
  **
  ** @param numberOfInts the number of random integers to generate and then
  **		sort.
  ** @param numberOfSortThreads the number of threads to be used to sort the
  **		the integers.  Each one will make its own accesses to the 
  **	    TupleSpace.
  ***************************************************************************
  */
  public MergeSort( int numberOfInts, String serverName ) {
    this( numberOfInts, serverName, DEFAULTMAXINTVALUE  );
  } // MergeSort


  /*
  ***************************************************************************
  ** ** MergeSort **
  ** ***************
  */
  /**
  ** Sort a set of randomly generated integers.
  **
  ** @param numberOfInts the number of random integers to generate and then
  **		sort.
  ** @param maxIntValue the maximum value of one of the randomly generated
  **		integers to be sorted.
  ** @param numberOfSortThreads the number of threads to be used to sort the
  **		the integers.  Each one will make its own accesses to the 
  **	    TupleSpace.
  ***************************************************************************
  */
  public MergeSort( int numberOfInts, String serverName, int maxIntValue ) {
    this( numberOfInts, serverName, maxIntValue, DEFAULTSPACENAME );
  } // MergeSort


  /*
  ***************************************************************************
  ** ** MergeSort **
  ** ***************
  */
  /**
  ** Sort a set of randomly generated integers.
  **
  ** @param numberOfInts the number of random integers to generate and then
  **		sort.
  ** @param maxIntValue the maximum value of one of the randomly generated
  **		integers to be sorted.
  ** @param numberOfSortThreads the number of threads to be used to sort the
  **		the integers.  Each one will make its own accesses to the 
  **	    TupleSpace.
  ** @param spaceName the name of the space to be used to do the sorting.
  ** @param serverName the name of the server that is managing the space.
  ***************************************************************************
  */
  public MergeSort( int numberOfInts, String serverName, 
		    int maxIntValue, String spaceName ) {

    this( numberOfInts, serverName, maxIntValue, spaceName, DEFAULTNUMSORTTHREADS );
		
  } // MergeSort

  /*
  ***************************************************************************
  ** ** MergeSort **
  ** ***************
  */
  /**
  ** Sort a set of randomly generated integers.
  **
  ** @param numberOfInts the number of random integers to generate and then
  **		sort.
  ** @param maxIntValue the maximum value of one of the randomly generated
  **		integers to be sorted.
  ** @param numberOfSortThreads the number of threads to be used to sort the
  **		the integers.  Each one will make its own accesses to the 
  **	    TupleSpace.
  ** @param spaceName the name of the space to be used to do the sorting.
  ** @param serverName the name of the server that is managing the space.
  ***************************************************************************
  */
  public MergeSort( int numberOfInts, String serverName, 
		    int maxIntValue, String spaceName,int numberOfSortThreads ) {

      this.numberOfInts	= numberOfInts;
      this.serverName	= serverName;
      this.maxIntValue	= maxIntValue;
      this.spaceName	= spaceName;
      this.numberOfSortThreads = numberOfSortThreads;
	    try {
        // Get the tuple space
        TupleSpace  ts  =  new TupleSpace( spaceName, serverName );
	      // Start up the threads that will do the actual sorting.      
        startSortThreads( ts, numberOfSortThreads );
	    }  catch( TupleSpaceException tse ) {
      Debug.out( tse );
      
    } // catch

      
  } // MergeSort


  /*
  ***************************************************************************
  ** ** addVectorsToSpace **
  ** ***********************
  */
  /**
  ** Create a set of Vectors of random integers.  The number of integers
  ** in each Vector is also random, but the total number of integers equals
  ** the parameter "numberOfInts".
  **
  ** @param ts the tuple space to be used to hold the values to be sorted
  ** @param numberOfInts the number of random integers to generate and then
  **			sort.
  ** @param maxIntValue the maximum value of one of the randomly generated
  **			integers to be sorted.
  ** @exception TupleSpaceException if there are problems using the 
  **			TupleSpace.
  ***************************************************************************
  */
  private void addVectorsToSpace(
    TupleSpace ts, 
    int numberOfInts, 
    int maxIntValue )
      throws TupleSpaceException
  {

    int	count		=	0; // Number of ints made so far
    Tuple multi = new Tuple();
    while ( count < numberOfInts ) {
      // Figure out the size of the Vector
      //int vSize = (int)Math.floor( Math.random() * (numberOfInts - count ) );
      int vSize = 1; // for now DAF

      // Must be at least 1
      vSize = ( vSize >= 1 ? vSize : 1 );	
      count += vSize;

      // Put the vector into the tuplespace.
      //ts.out( "data", makeRandomVector( vSize, maxIntValue ) );
      VectorWithEquals v = new VectorWithEquals();
      v.addElement( new Integer( count-1 ) );
      //Debug.out( "Adding " + (count-1) + ": " + v.toString() );
      //ts.write( new DataTuple( v ) );
      multi.add(new Field(new DataTuple(v)));

    } // while
    ts.multiWrite(multi);
    Debug.out("Wrote "+count+" tuples");
  } // addVectorsToSpace


  /*
  ***************************************************************************
  ** ** makeRandomVector **
  ** **********************
  */
  /**
  ** Create and return a Vector of random integers.
  **
  ** @param numberOfInts the number of random integers to generate.
  ** @param maxIntValue the maximum value the randomly generated
  **		integers.
  ***************************************************************************
  */
  private Vector makeRandomVector( int numberOfInts, int maxIntValue ) {

    VectorWithEquals retValue = new VectorWithEquals( numberOfInts );

    for ( int i = 0; i < numberOfInts; i++ ) {
      retValue.addElement( new Integer( (int) Math.floor( 
			     Math.round( 
			       Math.random() * maxIntValue ))));
    } // for

    Debug.out(" random vector..." + numberOfInts + " elements < " + maxIntValue );
    for (Enumeration e = retValue.elements(); e.hasMoreElements(); ) {
      Integer r = (Integer)e.nextElement();
      Debug.out( r.toString() );
    }
    return retValue;

  } // makeRandomVector


  /*
  ***************************************************************************
  ** ** startSortThreads **
  ** **********************
  */
  /**
  ** Create and start the execution of a specified number of threads to
  ** perform the merge sort.  
  **
  ** @param ts the tuple space being used to do the sorting.
  ** @param numberOfSortThreads the number of threads to be used to sort the
  **		the integers.  Each one will make its own accesses to the 
  **	    TupleSpace.
  ***************************************************************************
  */
  private void startSortThreads( TupleSpace ts, int numberOfSortThreads ) {
		_st = new SortThread[numberOfSortThreads];						  
    for ( int i = 0; i < numberOfSortThreads; i++ ) {
      _st[i] = new SortThread( ts, i );
      _st[i].start();
      
    } // for
		
  } // startSortThreads

  /*
  ***************************************************************************
  ** ** run **
  ** *********
  */
  /**
  ** Starting point of execution for thread.
  ***************************************************************************
  */
  public void run() {

    try {
      // Get the tuple space
      TupleSpace	ts	=	new TupleSpace( spaceName, serverName );
	    
      
      
      // Add Vectors of random integers to the tuple space.  The number of 
      // integers in each Vector is random, but the total number will equal
      // numberOfInts.
      int n = ts.deleteAll();  
      Debug.out("DeleteAll deleted "+n+" tuples.");
      
      addVectorsToSpace( ts, numberOfInts, maxIntValue );
      Debug.out("Placed "+numberOfInts+" tuples into space.");
      // Add the total number of integers to the space.
      ts.write( new CountTuple( numberOfInts ));

      
      DoneTuple result = null;
      DoneTuple template = new DoneTuple();
      Debug.out(0,template);
      // Now try to get the answer.
      while (result == null)  {
        int count = ts.countN(new DataTuple());
        if (count == 0)  {
          Debug.out(0,"ERROR _ No data tuples to be sorted.");
          //System.exit(1);
        } else  {
          Debug.out(0,"Still "+count+" tuples to be sorted");
        }
        // wait for 30 seconds to read a Done msg)
        result = (DoneTuple)ts.waitToRead( template,30*1000 );
        
      }
      // Print out the answer.
      Debug.out( "\nThe sorted integers are:" );
      Debug.out( result.getIntegers().toString() );
      for (int i=0;i<numberOfSortThreads;i++) {
        System.out.println("Thread "+i+" T1cnt="+_st[i].t1cnt+" T2cnt="+_st[i].t2cnt);
      }
      
     
      //ts.deleteAll();
      //ts.cleanup();
    } // try
    catch( TupleSpaceException tse ) {
      Debug.out( "Caught a TupleSpace Exception: \"" +
			 tse.getMessage() +   "\"" );
      tse.printStackTrace( System.out );
    } // catch

  } // run

  /*
  ***************************************************************************
  ** ** puase **
  ** ***********
  */ 
  /**
  ** Suspend the thread for the indicated number of seconds.  This is useful
  ** for giving a user enough time to read a message displayed on the 
  ** console before the server goes down
  **
  ** @param seconds the number of seconds to pause
  **************************************************************************
  */
  private static void pause( int seconds ) {
    try {
      Thread.sleep( seconds * 1000 );
    } // try
    catch( InterruptedException ie ) {}

  } // pause

  /*
  ***************************************************************************
  ** ** Main **
  ** **********
  */
  /**
  ** The starting point of execution for the merge sort.
  ***************************************************************************
  */
  public static void main( String argv[] ) {

    try {
      int 	numInts		=	DEFAULTNUMINTSTOSORT;	  	
      String	tsServerName	=	DEFAULTSERVERNAME;
      String  tsSpaceName = "mergesort";
      
      // standard processing of operands
      if ( argv.length == 0) 
        System.out.println("Usage:  Mergesort [-D] [-h tsHost] count");
      for (int i=0; i< argv.length; i++) {
        if (argv[i].equals("-D") )  {
          Debug.setDebugOn(true);
          //TupleSpace.setDebug(true);
        }  else if (argv[i].equals("-h")) {
          tsServerName = argv[++i];        
        } else         
          // if numeric than count
          try {
            numInts = Integer.parseInt( argv[i] );        
  
          } // try
          catch( NumberFormatException nfe ) {
            // Must be a host name
            tsServerName = argv[i];          
    
          } // catch
      }
    
     //if (Debug.isDebugOn()) 
	 	  //  ts.setDebug(true);

      
	  
	   long starttime = System.currentTimeMillis();
	   long totaltime;
      
      
      starttime = System.currentTimeMillis();
      int numSortThreads = 3;
      MergeSort	ms =	new MergeSort(  numInts, tsServerName, 1, 
           tsSpaceName, numSortThreads);
      ms.start();
      ms.join();	// wait until it's done
	    totaltime = System.currentTimeMillis() - starttime;
      System.out.println(numInts + " sorted.  Time : " + totaltime);
      // Get the tuple space
      //TupleSpace  ts  =  new TupleSpace( tsSpaceName, tsServerName );
      //ts.cleanup();
      Debug.out( "MergeSort ending" );
    } // try
    catch( Exception e ) {
      Debug.out( "Got Exception: \"" + e.getClass().getName() + "\" " + e.getMessage() );

    } // catch
    catch( Error err ) {
      Debug.out( "Got Error: \"" + err.getClass().getName() + "\" " + err.getMessage() );

    } // catch

    
    System.exit(0);
  
  } // main

} // MergeSort
/* $Log: MergeSort.java,v $
/* Revision 2.1.2.1  2000/08/30 12:54:18  jthomas
/* minor improvements to testcase
/*
/* Revision 2.3  2000/08/07 13:51:24  jthomas
/* changed to help find locking bug
/*
/* Revision 2.2  2000/07/28 15:16:25  jthomas
/* Improve testcase so itrecognizes error conditions
/* and terminates with an error message
/*
/* Revision 2.1  1999/11/05 22:22:38  estesp
/* Update revision number to 2.1 on all files
/*
/* Revision 1.1.1.1  1999/11/05 16:24:53  estesp
/* Imported 2.1.0 release into Austin CVS
/*
 * Revision 1.2  1999/06/17 05:39:39  thodes
 *   Updated the inital checkin to append the "Log" field and
 * convert CR/LF to CR (for win/unix interop).
 *
 *   The inital checkin lower-cased directrory names, and omitted
 * many dirs/files that will added later, e.g., MoDAL stuff.
 *
 * All of the above will need to be done to all VSS-to-CVS
 * converted sources.  In summary, in moving from VSS to CVS, do this:
 *  - lower-case dir names
 *  - CR/LF --> CR
 *  - append CVS "Log" entties
 *
 * (a script that helps with #2 and #3 is in
 *     tspaces1:~thodes/bin/update-keywords.sh)
 * 
 */


